package day75;

import java.util.*;

public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();
        // f[i][j] = f[i-1][j-1]+f[i-1][j]
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if(i==0 || j == i) {
                    row.add(1);
                } else {
                    row.add(ans.get(i-1).get(j-1)+ans.get(i-1).get(j));
                }
            }
            ans.add(row);
        }
        return ans;
    }
    public List<Integer> getRow(int rowIndex) {
//        List<Integer> pre = new ArrayList<>();
//        List<Integer> cur = new ArrayList<>();
//        for (int i = 0; i <= rowIndex; i++) {
//            for (int j = 0; j <= i; j++) {
//                if(j == 0 || i == j) {
//                    cur.add(1);
//                } else {
//                    cur.add(pre.get(j-1)+pre.get(j));
//                }
//            }
//            pre = cur;
//            cur = new ArrayList<>();
//        }
//        return pre;
        // 空间优化
        // f[i][j] = f[i-1][j-1]+f[i][j]
        // 倒叙遍历
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i <= rowIndex; i++) {
            for (int j = i; j >= 0; j--) {
                if(j == 0) ans.set(0,1);
                else if (j == i) ans.add(1);
                else ans.set(j,ans.get(j-1)+ans.get(j));
            }
        }
        return ans;
    }
//    public int maxProfit(int[] prices) {
//        // 动态规划
//        // 状态 持有这支股票 不持有这支股票
//        // dp[i][0]表示第i天持有这支股票
//        // dp[i][1]表示第i天不持有这支股票
//        // dp[i][0] = max(dp[i-1][0],-price[i])  不是第i天买的，就是前i-1天买的,dp[i-1][0]
//        // 第i天买的 就是-price[i]
//        //dp[i][1] = max(dp[i-1][0]+price[i],dp[i-1][1]);
//        // dp[0][0] = -price[0]
//        // dp[0][1] = 0;
//        int[][] dp = new int[prices.length][2];
//        dp[0][0] = -prices[0];
//        dp[0][1] = 0;
//        for (int i = 1; i < prices.length; i++) {
//            dp[i][0] = Math.max(dp[i-1][0],-prices[i]);
//            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
//        }
//        for (int i = 0; i < dp.length; i++) {
//            System.out.print(Arrays.toString(dp[i]));
//        }
//        return dp[dp.length-1][1];
////        Status pre = new Status();
////        Status cur = new Status();
////        pre.hold = -prices[0];
////        pre.disHold = 0;
////        for (int i = 1; i < prices.length; i++) {
////            cur.hold = Math.max(pre.hold, -prices[i]);
////            cur.disHold = Math.max(pre.disHold,pre.hold + prices[i]);
////            pre = cur;
////            cur = new Status();
////        }
////        return pre.disHold;
//    }
    public int maxProfit(int[] prices) {
        // 可以买卖多次
        // dp[i][0] = max(dp[i-1][0],dp[i-1][1]-price[i])
        // dp[i][1] = max(dp[i-1][1],dp[i-1][0]+price[i])
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
        }
        return dp[dp.length-1][1];
    }
//    public int[] countBits(int n) {
////        int[] ans = new int[n+1];
////        for (int i = 0; i <= n; i++) {
////            ans[i] = getBitCount(i);
////        }
////        return ans;
////        final int MAX = 1<<31;
////        int[] dp = new int[n+1];
////        for (int i = 1; i <= n; i++) {
////            if(MAX%i == 0) {
////                dp[i] = 1;
////            } else if (i%2 == 0) {
////                dp[i] = dp[i-1];
////            } else {
////                dp[i] = dp[i-1]+1;
////            }
////        }
////        return dp;
////        int[] dp = new int[n+1];
////        int highBit = 0;
////        for (int i = 1; i <= n; i++) {
////            if((i&(i-1)) == 0) highBit = i;
////            dp[i] = dp[i-highBit]+1;
////        }
////        return dp;
//        int[] dp = new int[n+1];
//        for (int i = 1; i <= n; i++) {
//            dp[i] = dp[i/2] + i%2;
//        }
//        return dp;
//    }
    public boolean isSubsequence(String s, String t) {
//        int i = 0,j = 0;
//        while (i<s.length()&&j<t.length()) {
//            if(s.charAt(i) == t.charAt(j)) i++;
//            j++;
//        }
//        return i == s.length();
        // 动态规划
        // dp[i][j] 表示以i-1为结尾 j-1为结尾的相同子序列的长度
        int[][] dp = new int[s.length()+1][t.length()+1];

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= t.length(); j++) {
                if(s.charAt(i-1) == t.charAt(j-1)) dp[i][j] = dp[i-1][j-1]+1;
                else dp[i][j] = dp[i][j-1];
            }
        }
        return dp[s.length()][t.length()] == s.length();
    }
//    public int minCostClimbingStairs(int[] cost) {
////        int n = cost.length;
////        int[] dp = new int[n+1]; // dp[i] 表示从到达第i层楼梯向上爬需要的最小花费
////        for (int i = 2; i <= n; i++) {
////         dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
////        }
////        return dp[n];
//        int pre = 0,cur = 0;
//        for (int i = 2; i <= cost.length; i++) {
//            int next = Math.min(cur+cost[i-1],pre+cost[i-2]);
//            pre = cur;
//            cur = next;
//        }
//        return cur;
//    }
    public boolean divisorGame(int n) {
        // 博弈问题
        // dp[x] 表示x的时候能不能赢 取决于 是否存在一个k 使得 x%k==0 && dp[x-k] = false;
        boolean[] dp = new boolean[n+3];
        dp[1] = false;
        dp[2] = true;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                if(i%j == 0 && dp[i-j] == false) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
    public int tribonacci(int n) {
        if(n <= 1) return n;
        if(n == 2) return 1;
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
        }
        return dp[n];
    }
    public int[] countBits(int n) {
        int[] dp = new int[n+1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i>>1]+(i&1);
        }
        return dp;
    }
    public int numWays(int n, int[][] relation, int k) {
        // dp[i][j] 表示编号i的玩家传递到n-1 传递j次的方法数
        // dp[i][j] += dp[children.get(x)][j-1]
        // dp[n][0] = 1;
//        List<Integer>[] graph = new List[n];
//        for (int i = 0; i < graph.length; i++) {
//            graph[i] = new ArrayList<>();
//        }
//        for (int[] rel: relation) {
//            graph[rel[0]].add(rel[1]);
//        }
//        int[][] dp = new int[n][k+1];
//        dp[n-1][0] = 1;
//        for (int j = 1; j <= k; j++) {
//            for (int i = 0; i < n; i++) {
//                for (int child: graph[i]) {
//                    dp[i][j] += dp[child][j-1];
//                }
//            }
//        }
//        for (int i = 0; i < dp.length; i++) {
//            System.out.println(Arrays.toString(dp[i]));
//        }
//        return dp[0][k];
//        List<Integer>[] graph = new List[n];
//        for (int i = 0; i < n; i++) {
//            graph[i] = new ArrayList<>();
//        }
//        for (int i = 0; i < relation.length; i++) {
//            graph[relation[i][0]].add(relation[i][1]);
//        }
//        return dfs(0,n,graph,k);
        List<List<Integer>> edges = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; i++) {
            edges.add(new ArrayList<Integer>());
        }
        for (int[] edge : relation) {
            int src = edge[0], dst = edge[1];
            edges.get(src).add(dst);
        }

        int steps = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0); // 从第0个节点开始遍历 遍历到第k层
        while (!queue.isEmpty() && steps<k) {
            steps++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int index = queue.poll();
                List<Integer> list = edges.get(index);
                for (int nextIndex : list) {
                    queue.offer(nextIndex);
                }
            }
        }
        int ways = 0;
        if (steps == k) {
            while (!queue.isEmpty()) {
                if (queue.poll() == n - 1) {
                    ways++;
                }
            }
        }
        return ways;
    }
    private int dfs(int cur,int n,List<Integer>[] graph,int k) {
        if(k == 0) {
            if(cur == n-1) return 1;
            return 0;
        }
        int ans = 0;
        for (int child: graph[cur]) {
            ans += dfs(child,n,graph,k-1);
        }
        return ans;
    }
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length+1];
        for (int i = 2; i <= cost.length; i++) {
            dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[cost.length];
    }
    public int trainWays(int num) {
        // 每次可以跳一个格子或者两个格子
        // dp[i] = dp[i-1]+dp[i-2]
        if(num == 0) return 1;
        if(num <= 2) return num;
        long MOD = 1000000007;
        long[] dp = new long[num+1];
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i < num; i++) {
            dp[i] = (dp[i-1]+dp[i-2])%MOD;
        }
        return (int) (dp[num]);
    }
    public int maxSales(int[] sales) {
        // dp[i] 表示以第i天结尾的销售总额的最大值
        // dp[i] = max(dp[i-1]+nums[i],nums[i])
        int[] dp = new int[sales.length];
        int ans = sales[0];
        dp[0] = sales[0];
        for (int i = 1; i < sales.length; i++) {
            dp[i] = Math.max(dp[i-1]+sales[i],sales[i]);
            ans = Math.max(ans,dp[i]);
        }
        return ans;
    }
    public int leastMinutes(int n) {
        int res = 0;
        while (true) {
            if(1<<res>=n) {
                return res+1;
            }
            res++;
        }
    }
    public String longestPalindrome(String s) {
        // dp[i][j] 表示i到j是不是回文子字符串
        // dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
        int n = s.length();
        int start = 0,end = 0;
        boolean[][] dp = new boolean[n][n];
        for (int i = n-1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if(j == i) dp[i][j] = true;
                else if (j == i+1 && s.charAt(i) == s.charAt(j)) dp[i][j] = true;
                else if (s.charAt(i) == s.charAt(j) && dp[i+1][j-1]) dp[i][j] = true;
                if(dp[i][j] && end-start+1 < j-i+1) {
                    start = i;
                    end = j;
                }
            }
        }
        return s.substring(start,end+1);
    }
    public int jump(int[] nums) {
        //
//        int n = nums.length;
//        int[] dp = new int[n];
//        Arrays.fill(dp,Integer.MAX_VALUE);
//        dp[0] = 0;
//        for (int i = 1; i < n; i++) {
//            for (int j = 0; j < i; j++) {
//                if(j + nums[j] >= i) {
//                    // 可以从这跳过来
//                    dp[i] = Math.min(dp[j]+1,dp[i]);
//                }
//            }
//        }
//        return dp[n-1];
        // 维护最前面的最小值
        // dp[i] = dp[i-pre] + 1;
//        int n = nums.length;
//        Queue<Integer> queue = new ArrayDeque<>();
//        int[] dp = new int[n];
//        Arrays.fill(dp,Integer.MAX_VALUE);
//        dp[0] = 0;
//        queue.offer(0);
//        for (int i = 1; i < n; i++) {
//            while (queue.peek() + nums[queue.peek()] < i) {
//                queue.poll();
//            }
//            // 肯定不为空
//            dp[n] = dp[queue.peek()]+1;
//            queue.offer(i);
//        }
//        return dp[n-1];
        // 贪心思路
        int len = nums.length;
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < len-1; i++) {
            maxPosition = Math.max(maxPosition,nums[i]+i); // 最远可以跳到的位置
            if(i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }
    public int maxSubArray(int[] nums) {
        // 最大子数组的和
        // dp[i] 表示第i个元素结尾的最大和
        int[] dp = new int[nums.length];
        int ans = nums[0];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
            ans = Math.max(ans,dp[i]);
        }
        return ans;
    }
    public boolean canJump(int[] nums) {
        //
//        int n = nums.length;
//        boolean[] dp = new boolean[n];
//        dp[0] = true;
//        for (int i = 0; i < n-1; i++) {
//            if(dp[i]) {
//                for (int j = 1; j <= nums[i] && i+j < n; j++) {
//                    dp[i+j] = true;
//                }
//            } else {
//                return false;
//            }
//        }
//        return dp[n-1];

        // 贪心 每次可以跳的最远距离
        int maxPos = 0; // 最远可以到达的位置
        for (int i = 0; i < nums.length; i++) {
            if(i<maxPos) {
                // i可以到达
                maxPos = Math.max(maxPos,i+nums[i]);
            } else {
                // i不能到达
                return false;
            }
        }
        return true;
    }
    public int uniquePaths(int m, int n) {
        // dp[i][j] 表示到达(i,j)点的路径数目
        // dp[i][j] = dp[i-1][j]+dp[i][j-1]
        // 初始化 dp[i][0] = 1
        // dp[0][j] = 1;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int[][] dp = new int[obstacleGrid.length][obstacleGrid[0].length];
        for (int i = 0; i < obstacleGrid.length; i++) {
            if (obstacleGrid[i][0] == 1){
                break;
            }
            dp[i][0] = 1;
        }
        for (int j = 0; j < obstacleGrid[0].length; j++) {
            if (obstacleGrid[0][j] == 1){
                break;
            }
            dp[0][j] = 1;
        }
        for (int i = 1; i < obstacleGrid.length; i++) {
            for (int j = 1; j < obstacleGrid[0].length; j++) {
                if(obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[dp.length-1][dp[0].length-1];
    }
    public int minPathSum(int[][] grid) {
        // 最小路径
        // dp[i][j] 表示到达 (i,j)位置的最小和
        // dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j]
        int m = grid.length,n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = grid[i][0] + dp[i-1][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = grid[0][j] + dp[0][j-1];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
    public int numDecodings(String s) {
        int n = s.length();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s.charAt(i - 1) != '0') {
                f[i] += f[i - 1];
            }
            if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
                f[i] += f[i - 2];
            }
        }
        return f[n];
    }
//    public List<String> generateParenthesis(int n) {
//        // 回溯
//        List<String> list = new ArrayList<>();
//        trackBack(new StringBuilder(),list,n*2);
//        return list;
//    }
//    private void trackBack(StringBuilder path,List<String> list,int n) {
//        if(path.length() == n) {
//            if(check(path.toString())) {
//                list.add(path.toString());
//            }
//            return;
//        }
//        StringBuilder newPath1 = new StringBuilder(path.toString());
//        newPath1.append("(");
//        trackBack(newPath1,list,n);
//
//        StringBuilder newPath2 = new StringBuilder(path.toString());
//        newPath2.append(")");
//        trackBack(newPath2,list,n);
//    }
//    // 检查是不是有效的括号组合
//    private boolean check(String s) {
//        System.out.println(s);
//        Stack<Character> stack = new Stack<>();
//        for (int i = 0; i < s.length(); i++) {
//            if(s.charAt(i) == ')') {
//                if(!stack.isEmpty()) stack.pop();
//                else return false;
//            } else {
//                stack.push('(');
//            }
//        }
//        return stack.isEmpty();
//    }
//    private int getBitCount(int n) {
//        int ans = 0;
//        while (n>0) {
//            n = n&(n-1);
//            ans++;
//        }
//        return ans;
//    }
    class Status {
        int hold;
        int disHold;
    }
}
